'''
牛客网
BM5 合并k个已排序的链表
'''
import sys
# 设置递归深度
sys.setrecursionlimit(100000)


class ListNode:
    def __init__(self,val,next = None):
        self.val = val
        self.next = next

class Solution:
    # 两个有序链表合并函数
    def Merge2(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # 一个已经为空了，直接返回另一个
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        # 加一个表头
        head = ListNode(0)
        cur = head
        # 两个链表都要不为空
        while pHead1 and pHead2:
            # 取较小值的节点
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                # 只移动取值的指针
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                # 只移动取值的指针
                pHead2 = pHead2.next
                # 指针后移
            cur = cur.next
            # 哪个链表还有剩，直接连在后面
        if pHead1:
            cur.next = pHead1
        else:
            cur.next = pHead2
        # 返回值去掉表头
        return head.next

        # 划分合并区间函数

    def divideMerge(self, lists: List[ListNode], left: int, right: int) -> ListNode:
        if left > right:
            return None
        # 中间一个的情况
        elif left == right:
            return lists[left]
        # 从中间分成两段，再将合并好的两段合并
        mid = (int)((left + right) / 2)
        return self.Merge2(self.divideMerge(lists, left, mid), self.divideMerge(lists, mid + 1, right))

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # k个链表归并排序
        return self.divideMerge(lists, 0, len(lists) - 1)


if __name__  == "__main__":
    pass
